There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
Example 1:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] Output: true Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Example 2:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2] Output: false Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.
Example 3:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1] Output: false
Constraints:
m == maze.lengthn == maze[i].length1 <= m, n <= 100maze[i][j]is0or1.start.length == 2destination.length == 20 <= startrow, destinationrow <= m0 <= startcol, destinationcol <= n- Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
- The maze contains at least 2 empty spaces.
Average Rating: 3.88 (72 votes)
Solution
Approach 1: Depth First Search
We can view the given search space in the form of a tree. The root node of the tree represents the starting position. Four different routes are possible from each position i.e. left, right, up or down. These four options can be represented by 4 branches of each node in the given tree. Thus, the new node reached from the root traversing over the branch represents the new position occupied by the ball after choosing the corresponding direction of travel.
In order to do this traversal, one of the simplest schemes is to undergo depth first search. In this case, we choose one path at a time and try to go as deep as possible into the levels of the tree before going for the next path. In order to implement this, we make use of a recursive function dfs(maze, start, desination, visited). This function takes the given maze array, the start position and the destination position as its arguments along with a visited array. visited array is a 2-D boolean array of the same size as that of maze. A True value at visited[i][j] represents that the current position has already been reached earlier during the path traversal. We make use of this array so as to keep track of the same paths being repeated over and over. We mark a True at the current position in the visited array once we reach that particular positon in the maze.
From every start position, we can move continuously in either left, right, upward or downward direction till we reach the boundary or a wall. Thus, from the start position, we determine all the end points which can be reached by choosing the four directions. For each of the cases, the new endpoint will now act as the new start point for the traversals. The destination, obviously remains unchanged. Thus, now we call the same function four times for the four directions, each time with a new start point obtained previously.
If any of the function call returns a True value, it means we can reach the desination.
The following animation depicts the process:
Complexity Analysis
-
Time complexity : O(mn). Complete traversal of maze will be done in the worst case. Here, m and n refers to the number of rows and coloumns of the maze.
-
Space complexity : O(mn). visited array of size m∗n is used.
Approach 2: Breadth First Search
Algorithm
The same search space tree can also be explored in a Depth First Search manner. In this case, we try to explore the search space on a level by level basis. i.e. We try to move in all the directions at every step. When all the directions have been explored and we still don't reach the destination, then only we proceed to the new set of traversals from the new positions obtained.
In order to implement this, we make use of a queue. We start with the ball at the start position. For every current position, we add all the new positions possible by traversing in all the four directions(till reaching the wall or boundary) into the queue to act as the new start positions and mark these positions as True in the visited array. When all the directions have been covered up, we remove a position value, s, from the front of the queue and again continue the same process with s acting as the new start position.
Further, in order to choose the direction of travel, we make use of a dir array, which contains 4 entries. Each entry represents a one-dimensional direction of travel. To travel in a particular direction, we keep on adding the particular entry of the dirs array till we hit a wall or a boundary. For a particular start position, we do this process of dir addition for all all the four directions possible.
If we hit the destination position at any moment, we return a True directly indicating that the destination position can be reached starting from the start position.
The following animation depicts the process:
Complexity Analysis
-
Time complexity : O(mn). Complete traversal of maze will be done in the worst case. Here, m and n refers to the number of rows and coloumns of the maze.
-
Space complexity : O(mn). visited array of size m∗n is used and queue size can grow upto m∗n in worst case.
Last Edit: October 10, 2018 6:43 PM
December 28, 2018 10:01 AM
Actually, DFS solution will not cause TLE error. You can copy the code and it will pass
Last Edit: September 27, 2018 10:51 AM
Very concise DFS solution :
class Solution {
private int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
return dfs(maze, visited, start, destination);
}
private boolean dfs(int[][] maze, boolean[][] visited, int[] c, int[] des) {
if (visited[c[0]][c[1]]) return false;
if (c[0] == des[0] && c[1] == des[1]) return true;
visited[c[0]][c[1]] = true;
boolean result = false;
for (int[] d : dir) {
int x = c[0] + d[0];
int y = c[1] + d[1];
while ( 0 <= x && x < maze.length && 0 <= y && y < maze[0].length && maze[x][y] == 0) {
x += d[0];
y += d[1];
}
result = result || dfs(maze, visited, new int[]{ x - d[0], y - d[1]}, des);
}
return result;
}
}
August 27, 2020 2:27 AM
I can see that the solutions above are incorrect. If we are not considering the direction from which we are coming from, we won't know if we will hit the wall or not (and thus stop at destination). Both of the above solutions return true as soon as the destination is reached without considering whether the ball can stop or not.
May 23, 2019 6:57 AM
Regardless of the running time, the DFS code is so messy.
Last Edit: January 11, 2020 1:58 AM
Why the running time of DFS is O(M*N)?
Last Edit: September 27, 2018 10:52 AM
I've implemented BFS as my first idea yet still I don't understand why tests make DFS fail due to TL. BFS in this case is more efficient yet they have same worst case time complexity so to be honest I don't necessarily agree with this decision.
July 2, 2019 8:40 AM
Seems like the use case:
[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]
[0,4]
[1,2]
is invalid.
Leetcode expected output: True.
In my opinion this should be: False. As the ball can keep rolling
Last Edit: October 13, 2018 8:18 AM
@vinod23
My dfs solution just got accepted.
Share my code and comments:
// dfs solution
class Solution {
private int[] dr;
private int[] dc;
private int[][] MAZE;
private int R;
private int C;
private int[] dest;
private boolean res;
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
dr = new int[]{-1, 1, 0, 0}; // u d l r
dc = new int[]{0, 0, -1, 1}; // u d l r
MAZE = maze;
R = maze.length;
C = maze[0].length;
dest = destination;
res = false;
// doesn't care the initial direction parameter
dfs(-1, start, new boolean[R][C]);
return res;
}
private void dfs(int dir, int[] start, boolean[][] visited) {
int r = start[0], c = start[1];
if (Arrays.equals(start, dest)) {
res = true;
return;
}
if (visited[r][c]) return;
visited[r][c] = true;
// up down left right
for (int i = 0; i < 4; ++i) {
if (i == dir) continue; // skip the direction that will hit the wall again
int x = r, y = c;
while (isValid(new int[]{x + dr[i], y + dc[i]})) {
x += dr[i];
y += dc[i];
}
dfs(i, new int[]{x, y}, visited);
}
}
// return true if the coord is valid and maze[coord] == 0;
private boolean isValid(int[] coord) {
int r = coord[0];
int c = coord[1];
if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (MAZE[r][c] == 1) return false;
return true;
}
}
August 23, 2020 11:07 PM
I have a dumb question, can anyone answer this, please?
Let's say we come up with the DFS approach in the interview for this very problem and if the interviewer says "Come up with an approach that takes the minimum path", should we do BFS? But both of the approaches take same time and space complexities, right?
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) { }};